Disk array devices recording data after adding redundant codes to the data have been developed to prevent loss of the data. Such disk array devices are generally classified, by the redundancy and control method, into six types from RAID0 to RAID5 (RAID: Redundant Arrays of Inexpensive Disks or Redundant Arrays of Independent Disks).
Further, recently, by implementing the technique based on the thesis disclosed in the following Nonpatent Document 1 into disk array devices, the disk array devices called RAID6, Double Parity and the like with multiple redundancies have also been realized.
[Nonpatent Document 1] James S. Plank, “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems” (Software-Practice and Experience, Volume 27, Number 9, September 1997, pp. 995-1012)
For a disk array device, it is possible to improve its reliability as a device by raising the redundancy and, by improving the reliability in this manner, it becomes possible to reduce the probability of occurrence of losing data which causes loss of the recorded information. However, since the redundancy is in a trade-off relation with the recording capacity of the device, raising the redundancy results in reducing the actual capacity usable to record information. Further, raising the redundancy gives rise to upsizing a computation circuit needed for computing redundant codes, and increasing the cost of the computation circuit. As a result, the unit price of the disk array device also increases.
For example, because the configuration of RAID1 has a high redundancy and almost does not need the redundant computation, it is used for the purpose of high reliability. The RAID1 is a method for recording the same data into two disk devices, and is therefore also referred to as mirroring.
However, in the RAID1, if such a case occurs as the two mirrored disk devices both fail to operate properly, then it is possible cause data loss. For example, when constituting a RAID with 12 disk devices, in the configuration of RAID1, if p represents the probability of failure of disk devices, then data loss occurs with the probability of 6×p×p. This means that data loss occurs only when failure has occurred in six different combinations of the mirrored disks among the 72 combinations of two arbitrary disks.
In order to deal with the failure of a plurality of disk devices as above, it is necessary to construct a disk array of the multiple-redundancy configuration based on the thesis of Nonpatent Document 1. For example, in the so-called RAID6 method, even if failure occurs in any two disk devices, it is still possible to recover the data.
However, even in the RAID6 method, if failure occurs in three disks or more, it is still possible to give rise to data loss.
Nonpatent Document 1 shows a method for configuring a disk array device capable of recovering data even if failure occurs in an arbitrary number m of disk devices. In more detail, Nonpatent Document 1 shows a method for assigning redundant codes by an analogous method to the Reed-Solomon code using a Galois extension field.
FIG. 9 serves to explain a method for implementing the method described in Nonpatent Document 1 into a number n of disk devices recording data (data disk devices), and disk array devices having the same number n of disk devices recording redundant codes (redundant disk devices). In FIG. 9, the operator T of a Galois extension field corresponds to the primitive root of the Galois extension field, while the index of T corresponds to other roots. Further, in Nonpatent Document 1 and Reed-Solomon code, the operators corresponding to the roots of a Galois extension field are expressed in the form of a transformation matrix T and powers of T.
FIG. 10 shows a specific example of implementing the method described in Nonpatent Document 1 into a disk array device having six redundant disk devices for six data disk devices. As shown in FIG. 10, gf (2^4) is used as the Galois extension field.
FIG. 11 serves to explain problems in the case of implementing the method described in the Nonpatent Document 1 as shown in FIG. 10 into disk array device. FIG. 11 shows a data recovery method when failure has occurred in the data disk devices d1 and d6, and the redundant disk devices c2, c3, c5, and c6.
As shown in FIG. 11, with respect to the rows with the redundant disk devices in failure, because it is impossible to use the redundant codes recorded in the redundant disk devices to recover the original data, rows with normal redundant disks device are used for data recovery. In order to carry out the data recovery, a submatrix is to be obtained by extracting the rows with the normal redundant disk devices and the operators at the intersection points with the rows with the data disk devices in failure. By finding the inverse matrix from the obtained submatrix, it is possible to obtain the data of the data disk devices in failure.
However, as shown in FIG. 11, because every element of the extracted submatrix is unanimously I and the matrix is singular, the inverse matrix is not available. That is, the data recovery cannot be carried out. Therefore, based on the method described in Nonpatent Document 1, in order to avoid the problem that the data recovery cannot be carried out, it is necessary to change the Galois extension field used for encoding to a field with a longer period. For example, using gf (2^8) can solve the above problem. However, this gives rise to another problem that gf (2^8) is more complicated in computation than gf (2^4), thereby resulting in a high cost for circuit implementation of the device, as well as a heavy load on computation.